/** 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 */

/**
 * 【方案一】dp删除记录
 * dp[i][j] 是 word1[i-1] word2[j-1] 最少删除次数
 * 1.word1[i-1]=word2[j-1] 不用删
 * dp[i][j] = dp[i-1][j-1];
 * 
 * 2.word1[j-1]!=word2[j-1] 要删
 * 2-1 删word1 dp[i][j] = dp[i-1][j]+1
 * 2-2 删word2 dp[i][j] = dp[i][j-1]+1
 * 2-3 删word1&world2 dp[i][j]=dp[i-1][j-1]+2 已经被包含了
 */
var minDistance = function(word1, word2) {
  const [m,n] = [word1.length, word2.length];
  const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
  for(let i=1;i<=m;i++) {
    dp[i][0]=i
  };
  for(let j=1;j<=n;j++) {
    dp[0][j] = j;
  }

  for(let i=1;i<=m;i++) {
    for(let j=1;j<=n;j++) {
      if(word1[i-1]==word2[j-1]) {
        dp[i][j] = dp[i-1][j-1];
      }else {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) +1;
      }
    }
  }
  return dp[m][n];
};
const word1 = "sea", word2 = "eat";
console.log('两个字符串的删除操作', minDistance(word1, word2))//2
/**
 * 【方案二】找到最长公共子序列的长度， 剩余的元素都要删掉
 *  res = w1.len+w2.len-2*LCS
 *  LCS:最长公共子序列
 */
var minDistance0 = function(word1, word2) {
  const [m, n] = [word1.length, word2.length];
  const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
  for(let i=1;i<=m;i++) {
    for(let j=1;j<=n;j++) {
      if(word1[i-1] == word2[j-1]) {
        dp[i][j] = dp[i-1][j-1]+1;
      }else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  return m+n-2*dp[m][n];
}
console.log('两个字符串的删除操作', minDistance0(word1, word2))//2
